/*
 * @lc app=leetcode.cn id=188 lang=golang
 *
 * [188] 买卖股票的最佳时机 IV
 */

// @lc code=start

func maxProfit(k int, prices []int) int {
	n := len(prices)
	buy := make([]int,k+1)
	for i,_:=range buy{
		buy[i] = math.MinInt32
	}
	sell := make([]int,k+1)
	for i:=0;i<n;i++{
		for j:=1;j<=k;j++{
			// 只看利润，购买股票的最大利润=之前售出股票获取的利润-当前股票的价格
			buy[j] = max(buy[j],sell[j-1]-prices[i])
			// 售出股票的利润 = 之前购买股票的利润+当前股票的价格
			// 这里之所以不是售出价格与购买价格相减
			// 是因为，我们保存的都是利润，已经将价格减掉了
			sell[j] = max(sell[j],prices[i]+buy[j])
		}

	}
	return sell[k]
}

func max(i,j int)int{
	if i>j{
		return i
	}
	return j
}

// @lc code=end
